package com.heima.algorithm.recursion;

/**
 * <h2>递归二分查找</h2>
 * <h2>子问题个数：1</h2>
 * <h2>子问题数据规模缩小倍数：2</h2>
 * <h2>除递归外执行的计算是：0</h2>
 * <h2>由log2为底1的对数为 0 == 0</h2>
 * <h2>时间复杂度：㏒n</h2>
 */
public class BinarySearch {

    /**
     * 对外界提供的递归二分查找
     * @param arr 待查找数组
     * @param target 待查找值
     * @return 查找到返回索引，没查找到返回-1
     */
    public static int binarySearch(int[] arr, int target){
        return binarySearch(arr,target,0,arr.length-1);
    }

    /**
     * 递归二分查找
     * @param arr 待查找数组
     * @param target 待查找值
     * @param start 起始索引（包含）
     * @param end 结束索引（包含）
     * @return 找到返回索引，找不到返回-1
     */
    private static int binarySearch(int[] arr, int target, int start, int end){
        if (start > end){
            return -1;
        }
        int median = (start + end) >>> 1;
        if (arr[median] < target){
            return binarySearch(arr,target,median + 1,end);
        }else if (target < arr[median]){
            return binarySearch(arr,target,start,median - 1);
        }else {
            return median;
        }
    }
}
